﻿using System;

namespace _21._合并两个有序链表
{
    /// <summary>
    /// https://leetcode.cn/problems/merge-two-sorted-lists/
    /// </summary>
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }

    public class Solution
    {
        public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {

            ListNode heads = new ListNode();

            if (l1 == null) return l2;
            if (l2 == null) return l1;

            ListNode nodes = heads;

            while (l1 != null && l2 != null)
            {
                if (l1.val <= l2.val)
                {
                    nodes.next = l1;
                    l1 = l1.next;
                }
                else if (l1.val > l2.val)
                {
                    nodes.next = l2;
                    l2 = l2.next;
                }
                nodes = nodes.next;
            }

            nodes.next = l1==null?l2:l1;
            return heads.next;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {

            var a = new ListNode(1, new ListNode(2, new ListNode(4)));
            var b = new ListNode(1, new ListNode(3, new ListNode(4)));
            ListNode listnode = new Solution().MergeTwoLists(a, b);
            Print(listnode);
            Console.WriteLine();

            listnode = new Solution().MergeTwoLists(null, null);
            Print(listnode);
            Console.WriteLine();

            listnode = new Solution().MergeTwoLists(null, new ListNode(0));
            Print(listnode);
            Console.WriteLine();
        }


        static void Print(ListNode node)
        {
            if (node == null) return;
            Console.Write(node.val);

            if (node.next != null)
            {
                Print(node.next);
            }

        }
    }
}
